import java.util.ArrayList;
import java.util.List;

/**
 * @program: data_structures_algorithms
 * @description: 二分查找，前提：数组是有序的
 * @author: lld
 * @create: 2020-10-13 16:55
 **/
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {12, 23, 34, 56, 100, 100, 100, 100, 345, 678, 900};
        List<Integer> integers = binarySearch(0, arr.length - 1, arr, 100);
        System.out.println(integers);
//        int search = binarySearch(0, arr.length - 1, arr, 900);
//        System.out.println(search);
    }
/**
 * @Description: 查找一个数
 * @Param: [left, right, arr, num]
 * @return: int
 **/
//    public static int binarySearch(int left, int right, int[] arr, int num) {
//        if (left > right) {
//            return -1;
//        }
//        int mid = (left + right) / 2;
//        if (arr[mid] > num) {
//            return binarySearch(left, mid - 1, arr, num);
//        } else if (arr[mid] < num) {
//            return binarySearch(mid + 1, right, arr, num);
//        } else {
//            return mid;
//        }
//    }

    /**
     * @Description: 可以查找相同的数
     * @Param: [left, right, arr, num]
     * @return: java.util.ArrayList<java.lang.Integer>
     **/
    public static ArrayList<Integer> binarySearch(int left, int right, int[] arr, int num) {
        ArrayList<Integer> list = new ArrayList<>();
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        if (arr[mid] > num) {
            return binarySearch(left, mid - 1, arr, num);
        } else if (arr[mid] < num) {
            return binarySearch(mid + 1, right, arr, num);
        } else {
//            往左遍历查找相同的数
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == arr[mid]) {
                list.add(temp);
                temp--;
            }
            list.add(mid);
//            往右遍历查找相同的数
            temp = mid + 1;
            while (temp < arr.length && arr[temp] == arr[mid]) {
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}
